package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         718,
		Discription: "最长公共子数组",
		Level:       2,
		Labels: map[string]int{
			"动态规划": 1,
		},
	})
}

func FindLength(nums1 []int, nums2 []int) int {
	//dp[i][j]表示nums1中以nums1[i-1]结尾的子数组、nums2中以nums2[j-1]结尾的子数组中最长的公共子数组
	dp := make([][]int, len(nums1)+1)
	for i := range dp {
		dp[i] = make([]int, len(nums2)+1)
	}

	res := 0
	for i := 1; i <= len(nums1); i++ {
		for j := 1; j <= len(nums2); j++ {
			if nums1[i-1] == nums2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
				res = max(res, dp[i][j])
			}
		}
	}

	return res
}
